package leetcode.图.拓扑排序;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/5 9:23
 * @description :https://leetcode-cn.com/problems/find-eventual-safe-states/
 */
public class
找到最终的安全状态 {
    @Test
    public void test() {
        Solution solution = new Solution();

    }

    class Solution {
        public List<Integer> eventualSafeNodes(int[][] graph) {
            int n = graph.length;
            List<List<Integer>> rg = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                rg.add(new ArrayList<>());
            }
            //存放每个节点的入度
            int[] inDeg = new int[n];
            for (int out = 0; out < n; out++) {
                for (int in : graph[out]) {
                    rg.get(in).add(out);
                }
                inDeg[out] = graph[out].length;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                if (inDeg[i] == 0) queue.offer(i);
            }
            while (!queue.isEmpty()) {
                int out = queue.poll();
                for (Integer in : rg.get(out)) {
                    if (--inDeg[in] == 0) {
                        queue.offer(in);
                    }
                }
            }
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                if (inDeg[i] == 0) {
                    list.add(i);
                }
            }
            return list;
        }
    }

}
